2009년04월11일 18번

[과목 구분 없음]
다음 문맥자유문법(CFG)에서 비단말기호 binary_digit가 생성하는 언어로 옳지 않은 것은?

① 01101
② 1101000
③ 001011
④ 1001011

(정답률: 45%)

문제 해설

비단말기호 binary_digit는 0 또는 1을 생성하는 기호입니다. 따라서 "01101"은 binary_digit로 생성 가능한 문자열입니다. "1101000", "001011", "1001011"도 모두 binary_digit로 생성 가능한 문자열입니다. 따라서 옳지 않은 것은 없습니다.

정답이 "01101"인 이유는 CFG에서 S → binary_digit S binary_digit | binary_digit 규칙에 따라, S는 binary_digit로 시작하고 끝나는 문자열이 됩니다. 그리고 S는 재귀적으로 binary_digit S binary_digit 또는 binary_digit로 확장될 수 있습니다. 따라서 "01101"은 S → binary_digit S binary_digit | binary_digit 규칙을 따라 생성 가능한 문자열 중 하나입니다.

이전 문제 다음 문제